11613. Наилучшее
время купить акции 2
Вам дан массив цен, где pricesi содержит цену имеющейся акции в i-ый день.
Каждый день Вы можете принять
решение о покупке и/или продаже акций. Одновременно Вы можете владеть не более
одной акцией.
Найдите максимальную прибыль,
которую можно получить.
Вход. Первая строка содержит размер n
(n ≤ 105) массива цен. Вторая строка содержит
массив цен – n целых чисел, каждое не более 104.
Выход. Выведите максимальную прибыль,
которую можно получить. Если прибыль получить невозможно, выведите 0.
Пример
входа 1 |
Пример
выхода 1 |
8 6 3 6 4 2 4 8 3 |
9 |
|
|
Пример
входа 2 |
Пример
выхода 2 |
4 5 5 3 2 |
0 |
жадный алгоритм
Рассмотрим как
меняется стоимость акции каждый день. Если при переходе от дня i – 1 ко дню i ее стоимость
растет, то разницу pricesi – pricesi – 1 включаем в общую
прибыль.
Пример
Рассмотрим первый тест.
Прибыль составит 3 + 6 = 9.
Реализация алгоритма
Читаем входные данные.
scanf("%d", &n);
prices.resize(n);
for (i = 0; i < n; i++)
scanf("%d", &prices[i]);
В
переменной res вычисляем максимальную возможную
прибыль.
res = 0;
for (int i = 1; i < prices.size(); i++)
Если
при переходе от дня i – 1 ко дню i стоимость акции растет, то
прибавляем к результату res прибыль prices[i] – prices[i – 1].
if (prices[i] > prices[i - 1])
res += prices[i] - prices[i - 1];
Выводим ответ.
printf("%d\n", res);
Читаем входные
данные.
n = int(input())
prices = list(map(int, input().split()))
В переменной res вычисляем максимальную возможную прибыль.
res = 0
for i in
range(1, len(prices)):
Если при переходе от дня i –
1 ко дню i стоимость акции растет, то
прибавляем к результату res прибыль prices[i] – prices[i – 1].
if
prices[i] > prices[i - 1]:
res += prices[i]
- prices[i - 1]
Выводим ответ.
print(res)